import java.util.*;

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 1、构建并存储图，初始化入度数组
        int[] in = new int[numCourses]; // 记录顶点的入度
        // 采用邻接表的方式(顶点 -> 出边)
        Map<Integer, List<Integer>> edges = new HashMap<>();
        for (int[] arr : prerequisites) {
            int a = arr[0], b = arr[1]; // b -> a
            if (!edges.containsKey(b)) {
                edges.put(b, new ArrayList<>());
            }
            edges.get(b).add(a);
            in[a]++;
        }
        // 2、拓扑排序
        // (1)将所有入度为0的顶点都加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                queue.offer(i); // 把顶点加入队列
            }
        }
        // (2)BFS
        int[] ret = new int[numCourses];
        int k = 0;
        while (!queue.isEmpty()) {
            int t = queue.poll();
            ret[k++] = t;
            // 删除入度为0的点的出边
            List<Integer> list = edges.get(t);
            if (list != null) {
                for (int x : list) {
                    // 如果删除之后，入度为0，就入队
                    if (--in[x] == 0) {
                        queue.offer(x);
                    }
                }
            }
        }
        // // (3)判断入度数组是否还存在值
        // for (int x : in) {
        //     if (x != 0) {
        //         return new int[]{};
        //     }
        // }
        // return ret;
        return k == numCourses ? ret : new int[]{};
    }
}